/**
  \file dawg_gnode.c
  \author Francis Girard
  \date 30 september 2013

  Dawg generator graph node used for generation.
*/


/*
 *  Copyright (C) 2013, Francis Girard
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */


#include "dawg_gnode.h"
#include "dawg_bits.h"
#include "polarssl/sha1.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>


/**
  A node into the suffix tree or the trie used for generation.
  */
typedef struct _dawg_gnode
{
    /// Parent nodes (after a reduction, a child may have multiple parents
    h_dawg_arr_node h_dawg_arr_node_parents;

    /// Child nodes
    h_dawg_arr_node h_dawg_arr_node_childs;

    /// Is this node an end of word ?
    dawg_bool_t bEndOfWord_;

    /// The letter value of this node
    unsigned char cValue_;

    /// The depth of the tree _under_ this node. If we are at the fringe, depth
    /// is 0, if the longest word under this node has 5 more letters, depth
    /// is 5.
    int nDepthGroup_;

    /// True iff this node is the last child of its parent (in parent's list)
    dawg_bool_t bEndOfDawgList_;

    /// The index of this node when tree is translated into a flat array.
    /// -1 if not translated yet.
    int nDawgIndex_;

    /// The computed hash value of this node
    unsigned char arrSha1_[E_DAWG_HASH_SIZE];

} dawg_gnode;



/**
  Creates an empty dawg node.
*/
h_dawg_gnode dawg_gnode_create_empty()
{
    dawg_gnode* pNewNode = (dawg_gnode*) malloc(sizeof(dawg_gnode));

    pNewNode->h_dawg_arr_node_parents = dawg_arr_node_create();
    pNewNode->h_dawg_arr_node_childs = dawg_arr_node_create();
    pNewNode->bEndOfWord_ = dawg_false;
    pNewNode->cValue_ = '\\';
    pNewNode->nDepthGroup_ = -1;
    pNewNode->bEndOfDawgList_ = dawg_false;
    pNewNode->nDawgIndex_ = -1;

    return pNewNode;
}


/**
  Creates a dawg node.
*/
h_dawg_gnode dawg_gnode_create(unsigned char cValue, int depthGroup, h_dawg_gnode hParentNode)
{
    dawg_gnode* pNewNode = (dawg_gnode*) malloc(sizeof(dawg_gnode));

    pNewNode->h_dawg_arr_node_parents = dawg_arr_node_create();
    pNewNode->h_dawg_arr_node_childs = dawg_arr_node_create();
    pNewNode->bEndOfWord_ = dawg_false;
    pNewNode->cValue_ = cValue;
    pNewNode->nDepthGroup_ = depthGroup;
    pNewNode->bEndOfDawgList_ = dawg_false;
    pNewNode->nDawgIndex_ = -1;

    dawg_arr_node_push_back(pNewNode->h_dawg_arr_node_parents, hParentNode);

    return pNewNode;
}


dawg_bool_t dawg_gnode_isEow(h_dawg_gnode hNode)
{
    dawg_gnode* pNode = (dawg_gnode*) hNode;
    assert(pNode);
    return pNode->bEndOfWord_;
}


dawg_bool_t dawg_gnode_isEoList(h_dawg_gnode hNode)
{
    dawg_gnode* pNode = (dawg_gnode*) hNode;
    assert(pNode);
    return pNode->bEndOfDawgList_;
}


unsigned char dawg_gnode_get_cval(h_dawg_gnode hNode)
{
    dawg_gnode* pNode = (dawg_gnode*) hNode;
    assert(pNode);
    return pNode->cValue_;
}


int dawg_gnode_get_depth(h_dawg_gnode hNode)
{
    dawg_gnode* pNode = (dawg_gnode*) hNode;
    assert(pNode);
    return pNode->nDepthGroup_;
}


/**
  Destroys a dawg node.
*/
void dawg_gnode_destroy(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;

  //
  // Destroy our childs
  //
  if (1) // FIXME
  {
    h_dawg_arr_node_it itChildCur = dawg_arr_node_last(pNode->h_dawg_arr_node_childs);
    h_dawg_arr_node_it itBeforeBegin = dawg_arr_node_before_begin(pNode->h_dawg_arr_node_childs);
    for ( ; itChildCur != itBeforeBegin; itChildCur-- )
    {
      dawg_gnode_destroy(*itChildCur);
    }
  }

  //
  // Destroy the array containers
  //
  dawg_arr_node_destroy(pNode->h_dawg_arr_node_childs);
  dawg_arr_node_destroy(pNode->h_dawg_arr_node_parents);
}




/**
  Recursively computes the hash value of this nodes and all of its children.
*/
h_dawg_arr_unsigned_char dawg_gnode_calculate_hash
(
  h_dawg_gnode hNode,
  h_dawg_arr_unsigned_char hBrothersHash
)
{
  //
  // 1- Will be filled with the hash value of children, one after the other,
  //    starting from the last to the first;
  // 2- It also plays the role of brothers hash to compute children hash value.
  //    This means that the hash value of a node which depends on the hash
  //    value of its brothers depends in fact on the brothers at the right of
  //    that node.
  // 3- After having calculated the hash value of children and inserted them
  //    into our own hashInput, insert our own basic infos into the hash and
  //    finally the hash of our brothers as input.
  // 4- Compute the hash value based on all this, i.e. childs' hash'es, letter
  //    value, end of word, brothers' hashes.
  //

  //
  // This is a very very important choice here! Child nodes are sorted
  // alphabetically. Then we represent the hash value of a node, i.e. its
  // comparison value as the infos contained in that node, its children,
  // plus the infos contained in the following siblings.
  //
  // It is by no mean the best way to group the nodes in order to reduce
  // the size of the tree by tracking identical subtrees _without_ changing
  // the search algorithm (or very little)
  //
  // For example we may reduce more in changing the order of the siblings
  // or by allowing smaller subgroup units.
  //
  //
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  h_dawg_arr_unsigned_char hashInput = dawg_arr_unsigned_char_create();

  //
  // We're iterating through children backwards, so the intermediate values of
  // hashInput are in fact brothersHash of successive children.
  //
  h_dawg_arr_node_it itChildCur = dawg_arr_node_last(pNode->h_dawg_arr_node_childs);
  h_dawg_arr_node_it itBeforeBegin = dawg_arr_node_before_begin(pNode->h_dawg_arr_node_childs);
  for ( ; itChildCur != itBeforeBegin; itChildCur-- )
  {
      // Recursively calculate the hash value for this child. hashInput are the
      // "brothers", i.e. those node coming after this child in this child's list.
      h_dawg_arr_unsigned_char arrSha1CurChild = dawg_gnode_calculate_hash(*itChildCur, hashInput);

      // Insert this children hash value at the end of hash input.
      dawg_arr_unsigned_char_append(hashInput, arrSha1CurChild);
  }

  //
  // When here, hashInput contains the hash values of all the childs.
  // And that's all.
  //

  //
  // Put our very own infos into hash input, i.e. letter value, end of word,
  // and computed hash value from our brothers as we've got as parameter.
  //
  dawg_arr_unsigned_char_push_back(hashInput, pNode->cValue_);
  dawg_arr_unsigned_char_push_back(hashInput, pNode->bEndOfWord_);
  dawg_arr_unsigned_char_append(hashInput, hBrothersHash);

  //
  // And finally compute the hash value
  //
  sha1( hashInput, dawg_arr_unsigned_char_size(hashInput), pNode->arrSha1_ );

  //
  // Cleaning
  //
  dawg_arr_unsigned_char_destroy(hashInput);
}


/**
  Recursively linearize the tree structure starting at the specified root.

  The specified root node itself is excluded.
*/
void dawg_gnode_index_nodes(h_dawg_gnode h_root, h_dawg_arr_node hIndexedNodes)
{
  dawg_gnode* pRoot = (dawg_gnode*) h_root;
  assert(pRoot);

  //
  // If root has children and not a reducing copy coming from somewhere else and not already done
  //
  if ( dawg_arr_node_is_empty(pRoot->h_dawg_arr_node_childs) &&
       ((dawg_gnode*) dawg_arr_node_front(pRoot->h_dawg_arr_node_childs))->nDawgIndex_ == -1 )
  {
    //
    // Linearize the childs themselves
    //
    h_dawg_arr_node_it itCur = dawg_arr_node_begin(pRoot->h_dawg_arr_node_childs);
    h_dawg_arr_node_it itEnd = dawg_arr_node_end(pRoot->h_dawg_arr_node_childs);
    for ( ; itCur != itEnd; ++itCur )
    {
      ((dawg_gnode*)*itCur)->nDawgIndex_ = dawg_arr_node_size(hIndexedNodes) + 1;
      dawg_arr_node_push_back(hIndexedNodes, *itCur);
    }

    //
    // Linearize the subtrees under the childs
    //
    itCur = dawg_arr_node_begin(pRoot->h_dawg_arr_node_childs);
    itEnd = dawg_arr_node_end(pRoot->h_dawg_arr_node_childs);
    for ( ; itCur != itEnd; ++itCur)
    {
      dawg_gnode_index_nodes(*itCur, hIndexedNodes);
    }
  }

}


/**
  Recursively mark the first and last childs (in their parent's list).
*/
void dawg_gnode_mark_first_and_last_child(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  if (!dawg_arr_node_is_empty(pNode->h_dawg_arr_node_childs))
  {
    ((dawg_gnode*)dawg_arr_node_last(pNode->h_dawg_arr_node_childs))->bEndOfDawgList_ = dawg_true;

    h_dawg_arr_node_it itChilds = dawg_arr_node_begin(pNode->h_dawg_arr_node_childs);
    h_dawg_arr_node_it itEnd = dawg_arr_node_end(pNode->h_dawg_arr_node_childs);
    for ( ; itChilds != itEnd; ++itChilds)
    {
      dawg_gnode_mark_first_and_last_child(*itChilds);
    }
  }
}


/**
  Find all the nodes with the requested depth.

  Note that during or after reduction, a node may have
  more than one parent and therefore, if we simply and
  classical traverse the tree, the exact same node may
  occur twice. Therefore we store them into a "unique set".
*/
void dawg_gnode_find_nodes_at_depth(h_dawg_gnode hNode, int depth, h_dawg_unique_node_set result)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;

  h_dawg_arr_node_it itCur = dawg_arr_node_begin(pNode->h_dawg_arr_node_childs);
  h_dawg_arr_node_it itEnd = dawg_arr_node_end(pNode->h_dawg_arr_node_childs);

  /* Children nodes are ordered first by their depth, then alphabetically  */
  for ( ; itCur != itEnd; ++itCur)
  {
    if (depth <= ((dawg_gnode*)*itCur)->nDepthGroup_)
    {
      if (depth == ((dawg_gnode*)*itCur)->nDepthGroup_)
      {
        dawg_unique_node_set_add(result, *itCur);
      }

      // If requested depth is less than this child's depth, we will find a node
      // with requested depth by going deeper.
      dawg_gnode_find_nodes_at_depth(*itCur, depth, result);
    }

    //
    // Theoretically, we should be able to do this :
    // (Since childs are naturally ordered by length when building the trie)
    //
    // else
    // {
    //   break;
    // }
    //
  }
}


/**
  Determines whether the two specified nodes have the hash value.
*/
dawg_bool_t dawg_gnode_same_hash(h_dawg_gnode hNode1, h_dawg_gnode hNode2)
{
  dawg_gnode* pNode1 = (dawg_gnode*) hNode1;
  dawg_gnode* pNode2 = (dawg_gnode*) hNode2;
  assert(pNode1);
  assert(pNode2);

  return memcmp(pNode1->arrSha1_, pNode2->arrSha1_, E_DAWG_HASH_SIZE) == 0;
}


/**
  Get the siblings at the right of the specified node, that specified node included.
*/
void dawg_gnode_get_right_siblings(h_dawg_gnode hNode, h_dawg_arr_node hOutArray)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  //
  // First find the specified hNode into parent's child list ...
  //
  assert(dawg_arr_node_size(pNode->h_dawg_arr_node_parents) > 0);
  dawg_gnode* pParent = (dawg_gnode*) dawg_arr_node_front(pNode->h_dawg_arr_node_parents);
                        // Just take the first parent, anyone will do.


  h_dawg_arr_node_it itCur = dawg_arr_node_begin(pParent->h_dawg_arr_node_childs);
  h_dawg_arr_node_it itEnd = dawg_arr_node_end(pParent->h_dawg_arr_node_childs);
  for ( ; itCur != itEnd && *itCur != hNode; itCur++ ) ;

  //
  // We should find it all the time otherwise this is a mistake
  //
  assert(itCur != itEnd);

  //
  // From now on, we copy all the child nodes we are iterating
  // into the output array.
  //
  for ( ; itCur != itEnd; itCur++ )
  {
      dawg_arr_node_push_back(hOutArray, *itCur);
  }
}


/**
  Blindly substitute a direct child for another.
  @param hParentNode The parent node for which we want to substitute a child.
  @param hChildNodeToRm The child node that must be substituted.
  @param hChildNodeReplaceant The new child node that should replace "hChildNodeToRm".
  @return True iff the child node to substitute has been found and substituted.
  */
dawg_bool_t dawg_gnode_substitute_child(h_dawg_gnode hParentNode,
                                        h_dawg_gnode hChildNodeToRm,
                                        h_dawg_gnode hChildNodeReplaceant)
{
  dawg_gnode* pParentNode = (dawg_gnode*) hParentNode;
  dawg_gnode* pChildNodeToRm = (dawg_gnode*) hChildNodeToRm;
  dawg_gnode* pChildNodeReplaceant = (dawg_gnode*) hChildNodeReplaceant;
  assert(pParentNode);
  assert(pChildNodeToRm);
  assert(pChildNodeReplaceant);

  dawg_bool_t bReturn = dawg_arr_node_substitute(pParentNode->h_dawg_arr_node_childs,
                                                 hChildNodeToRm,
                                                 hChildNodeReplaceant);
  return bReturn;
}


/**
  Adds the specified new parents to the specified node.

  That is it only adds the new parents to its internal parent's list without
  taking care of the rest of the tree.
  */
void dawg_gnode_add_parents(h_dawg_gnode hNode, h_dawg_arr_node hArrNewParents)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  //
  // Check there is no redundant parents
  //
  h_dawg_arr_node hArrNewParentsCpy = dawg_arr_node_create();
  h_dawg_arr_node_it itNewCur = dawg_arr_node_begin(hArrNewParents);
  h_dawg_arr_node_it itNewEnd = dawg_arr_node_end(hArrNewParents);
  for ( ; itNewCur != itNewEnd; itNewCur++ )
  {
    h_dawg_arr_node_it itCur = dawg_arr_node_begin(pNode->h_dawg_arr_node_parents);
    h_dawg_arr_node_it itEnd = dawg_arr_node_end(pNode->h_dawg_arr_node_parents);
    for ( ; itCur != itEnd && *itCur != *itNewCur; itCur++ ) ;

    if (itCur == itEnd)
    {
      // Ok no duplicates found ...
      dawg_arr_node_push_back(hArrNewParentsCpy, *itNewCur);
    }
  }

  // Copy the non duplicates new parents
  dawg_arr_node_append(pNode->h_dawg_arr_node_parents, hArrNewParentsCpy);

  // Clean
  dawg_arr_node_destroy(hArrNewParentsCpy);
}


/**
  Substitute a node with another when they are equivalent.
  */
void dawg_gnode_reduce_node(h_dawg_gnode hToRm, h_dawg_gnode hNodeSubstitute)
{
    h_dawg_arr_node hArrSiblingsToRm = dawg_arr_node_create();
    h_dawg_arr_node hArrSubstituteSiblings = dawg_arr_node_create();

    dawg_gnode_get_right_siblings(hToRm, hArrSiblingsToRm);
    dawg_gnode_get_right_siblings(hNodeSubstitute, hArrSubstituteSiblings);

    //
    // Re-wire the parent-child relationship of all the siblings
    //
    h_dawg_arr_node_it itSiblingsToRmCur = dawg_arr_node_begin(hArrSiblingsToRm);
    h_dawg_arr_node_it itSiblingsToRmEnd = dawg_arr_node_end(hArrSiblingsToRm);
    h_dawg_arr_node_it itSiblingsSubstituteCur = dawg_arr_node_begin(hNodeSubstitute);

    for ( ; itSiblingsToRmCur != itSiblingsToRmEnd; itSiblingsToRmCur++, itSiblingsSubstituteCur++ )
    {
        // The parents of itSiblingsToRmCur are now parents of itSiblingsSubstituteCur
        dawg_gnode_add_parents(*itSiblingsSubstituteCur,
                              ((dawg_gnode*)*itSiblingsToRmCur)->h_dawg_arr_node_parents);

        // Each of the parent now has a new child instead of the old one.
        // Oh my god! Computers are fun!
        h_dawg_arr_node_it hNodeItCur = dawg_arr_node_begin(((dawg_gnode*)*itSiblingsToRmCur)->h_dawg_arr_node_parents);
        h_dawg_arr_node_it hNodeItEnd = dawg_arr_node_end(((dawg_gnode*)*itSiblingsToRmCur)->h_dawg_arr_node_parents);
        for ( ; hNodeItCur != hNodeItEnd; hNodeItCur++ )
        {
            dawg_gnode_substitute_child(*hNodeItCur,
                                        *itSiblingsToRmCur,
                                        *itSiblingsSubstituteCur);
        }
    }

    //
    // If somewhere along the branch, there is a node having a parent outside the branch,
    // we must relink it ...
    //
    // Quite difficult thing to do...
    //
    // But the case should never occur if we consider that :
    //   - When the trie is first constructed, it is constructed completely unfold,
    //   - that means identical subtrees are necessarily duplicated,
    //   - which means that no node in a subtree should have a parent outside the deleted tree
    //   - Furthermore,
    //   -   If we proceed by eliminating the longest or deepest trees first, then this
    //       property that no subtree linked to a parent outside the tree should remain
    //       true all the time
    //
    // Therefore, we don't do the hard and difficult relinking here since it is
    // not necessary.
    //
    // But should we change the "deepest" first elimination rule, then we would
    // have no choice than to reconsider and do this hard relinking.
    //

    //
    // Destroy the node and branch that has been substituted since it is now completely
    // isolated.
    //
    dawg_gnode_destroy(hToRm);

    //
    // Cleaning: destroy temp arrays
    //
    dawg_arr_node_destroy(hArrSiblingsToRm);
    dawg_arr_node_destroy(hArrSubstituteSiblings);
}


/**
  Binary encoding of the specified node on 4 bytes.
  @return The encoded value of the node.
*/
int dawg_gnode_encoded(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);
  assert(pNode->nDawgIndex_ != -1);

  //
  // First encode the index of the childs
  //
  int result = dawg_arr_node_is_empty(pNode->h_dawg_arr_node_childs) ? 0 :
               ((dawg_gnode*) dawg_arr_node_front(pNode->h_dawg_arr_node_childs))->nDawgIndex_;
  assert(result != -1);
  result <<= E_DAWG_CHILD_BIT_SHIFT;

  //
  // Second encode the letter value of this node
  //
  result += pNode->cValue_;

  //
  // Finally encode the end of word and end of list flags
  //
  if (pNode->bEndOfWord_)
    result += E_DAWG_END_OF_WORD_FLAG;
  if (pNode->bEndOfDawgList_)
    result += E_DAWG_END_OF_LIST_FLAG;

  return result;
}


/**
  Find a direct child with the specified character value.
*/
h_dawg_gnode dawg_gnode_find_child(h_dawg_gnode hNode, unsigned char childValue)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);
  h_dawg_gnode hChildNode = 0; // NULL

  h_dawg_arr_node_it itChildCur = dawg_arr_node_begin(pNode->h_dawg_arr_node_childs);
  h_dawg_arr_node_it itChildEnd = dawg_arr_node_end(pNode->h_dawg_arr_node_childs);

  for ( ; itChildCur != itChildEnd &&
          ((dawg_gnode*)*itChildCur)->cValue_ != childValue
        ; itChildCur++) ;

  if (itChildCur != itChildEnd)
  {
      hChildNode = *itChildCur;
  }

  return hChildNode;
}


/**
  Get the number of direct childs.
*/
unsigned int dawg_gnode_get_nb_childs(h_dawg_gnode hNode)
{
    dawg_gnode* pNode = (dawg_gnode*) hNode;
    assert(pNode);
    return dawg_arr_node_size(pNode->h_dawg_arr_node_childs);
}


/**
  Adds a new child value to the specified node.
*/
h_dawg_gnode dawg_gnode_add_child(h_dawg_gnode h_parent_node, unsigned char childValue, int depthGroup)
{
  dawg_gnode* p_parent_node = (dawg_gnode*) h_parent_node;
  assert(p_parent_node);
  h_dawg_gnode hNewChild = dawg_gnode_create(childValue, depthGroup, h_parent_node);
  dawg_arr_node_push_back(p_parent_node->h_dawg_arr_node_childs, hNewChild);
  return hNewChild;
}


/**
  Builds a classical trie (prefix tree) from the specified list of words.

  @param h_input_words The list of words ordered by length and then alphabetically.
  @return The root node.
*/
h_dawg_gnode dawg_gnode_build_trie_(h_dawg_gnode h_root_node, h_dawg_arr_str h_input_words)
{
  // Parcouring the list in reverse order, that is the longest words first
  // and then in reverse alphabetical order
  h_dawg_arr_str_it itWord = dawg_arr_str_before_begin(h_input_words);
  h_dawg_arr_str_it itEnd = dawg_arr_str_end(h_input_words);

  if (itWord != itEnd)
  {
    itEnd--; // One before last
  }

  for ( ; itWord != itEnd; --itWord)
  {
    // The depth _under_ the current node
    int nCurrentDepth = strlen(*itWord) - 1;
    h_dawg_gnode h_cur_node = h_root_node;

    char* itLetterCur = *itWord;
    char* itLetterEnd = (*itWord) + (nCurrentDepth+1);

    for ( ; itLetterCur != itLetterEnd; ++itLetterCur)
    {
      // If we found a child with the same letter here then we are sure that
      // it has a greater depth or equal depth since input words are given
      // ordered first by depth. Hence we don't have to take care to update
      // the node's depth : we are sure that it is less or equal
      h_dawg_gnode hNextNode = dawg_gnode_find_child(h_cur_node, *itLetterCur);

      if (hNextNode == NULL)
      {
        // Final depth for this node since it is impossible to have a greater
        // depth, the way the nodes are ordered.
        h_dawg_gnode hNewNode = dawg_gnode_add_child(h_cur_node, *itLetterCur, nCurrentDepth);
        h_cur_node = hNewNode;
      }
      else
      {
        h_cur_node = hNextNode;
      }

      // Decrement the depth since we just "ate" the first letter
      --nCurrentDepth;
    }


    ((dawg_gnode*) h_cur_node)->bEndOfWord_ = dawg_true;
  }
}


/**
  Builds a classical trie (prefix tree) from the specified list of words.

  @param h_input_words The list of words ordered by length and then alphabetically.
  @return The root node.
*/
h_dawg_gnode dawg_gnode_build_trie(h_dawg_gnode h_root_node, h_dawg_arr_str h_input_words)
{
  // Parcouring the list in reverse order, that is the longest words first
  // and then in reverse alphabetical order
  h_dawg_arr_str_it itWord = dawg_arr_str_begin(h_input_words);
  h_dawg_arr_str_it itEnd = dawg_arr_str_end(h_input_words);

  for ( ; itWord != itEnd; itWord++)
  {
    // The depth _under_ the current node
    int nCurrentDepth = strlen(*itWord) - 1;
    h_dawg_gnode h_cur_node = h_root_node;

    // Reset the depth of the root node if current depth is greater
    if (nCurrentDepth+1 > ((dawg_gnode*) h_cur_node)->nDepthGroup_)
    {
        ((dawg_gnode*) h_cur_node)->nDepthGroup_ = nCurrentDepth+1;
    }

    char* itLetterCur = *itWord;
    char* itLetterEnd = (*itWord) + (nCurrentDepth+1);

    for ( ; itLetterCur != itLetterEnd; ++itLetterCur, --nCurrentDepth)
    {
      h_dawg_gnode hNextNode = dawg_gnode_find_child(h_cur_node, *itLetterCur);

      if (hNextNode == NULL)
      {
        // We must insert a new child to this parent node
        h_dawg_gnode hNewNode = dawg_gnode_add_child(h_cur_node, *itLetterCur, nCurrentDepth);
        h_cur_node = hNewNode;
      }
      else
      {
        h_cur_node = hNextNode;
        // Reset the depth of the current node if current depth is greater
        if (nCurrentDepth > ((dawg_gnode*) h_cur_node)->nDepthGroup_)
        {
            ((dawg_gnode*) h_cur_node)->nDepthGroup_ = nCurrentDepth;
        }
      }
    }

    ((dawg_gnode*) h_cur_node)->bEndOfWord_ = dawg_true;
  }
}


/**
  Compare two nodes based on its hash value.

  @param hNode1 First node to compare
  @param hNode2 Second node to compare
  @return 0 if equal, >0 is first node is greater and <0 otherwise.
  */
static int _cmpNodesByHash(const void* hNode1, const void* hNode2)
{
    const dawg_gnode* pNode1 = *(const dawg_gnode**) hNode1;
    const dawg_gnode* pNode2 = *(const dawg_gnode**) hNode2;

    return pNode1->arrSha1_ - pNode2->arrSha1_;
}


/**
  Reduce graph redundant nodes.

  The root node is this.

  @param nMaxNodeDepth The maximum depth under a node in the complete tree, this
                       corresponds to the number of letters in the longest word,
                       minus 1.
*/
void dawg_gnode_reduce_graph(h_dawg_gnode hRootNode, int nMaxNodeDepth)
{
  //
  // For all the depth (word length), starting with the greatest
  //
  int nCurrentDepth = nMaxNodeDepth;
  for ( ; nCurrentDepth >= 0; --nCurrentDepth)
  {
    printf("Depth %2d: ", nCurrentDepth);

    //
    // Collect all the nodes of the current depth ...
    //
    h_dawg_unique_node_set hUniqueNodes = dawg_unique_node_set_create();
    dawg_gnode_find_nodes_at_depth(hRootNode, nCurrentDepth, hUniqueNodes);

    h_dawg_arr_node hArrNodesAtThisDepth = dawg_arr_node_create();
    dawg_unique_node_set_linearize(hUniqueNodes, hArrNodesAtThisDepth);
    dawg_unique_node_set_destroy(hUniqueNodes);

    unsigned int nNbNodes = dawg_arr_node_size(hArrNodesAtThisDepth);

    printf("%d nodes\n", nNbNodes);

    //
    // Try to reduce the tree if there is more than one node at this depth.
    //
    if (nNbNodes > 1)
    {
        // Sort the array by hash value
        dawg_arr_node_sort(hArrNodesAtThisDepth, _cmpNodesByHash);

        h_dawg_arr_node_it itNodeThisDepthCur = dawg_arr_node_begin(hArrNodesAtThisDepth);
        h_dawg_arr_node_it itNodeThisDepthEnd = dawg_arr_node_end(hArrNodesAtThisDepth);

        for ( ; itNodeThisDepthCur != itNodeThisDepthEnd; itNodeThisDepthCur++)
        {
            unsigned char* pCurHash = ((dawg_gnode*)(*itNodeThisDepthCur))->arrSha1_;
            h_dawg_arr_node_it itNodeThisDepthToKeep = itNodeThisDepthCur;

            //
            // Try to find all the consecutive nodes with the same hash value
            // They will be in [itNodeThisDepthToKeep, itNodeThisDepthSameHashEnd)
            //
            h_dawg_arr_node_it itNodeThisDepthSameHashEnd = itNodeThisDepthCur;
            itNodeThisDepthCur++;
            for ( ; itNodeThisDepthCur != itNodeThisDepthEnd &&
                    memcmp(pCurHash, ((dawg_gnode*)(*itNodeThisDepthCur))->arrSha1_, E_DAWG_HASH_SIZE) == 0
                  ; itNodeThisDepthSameHashEnd++, itNodeThisDepthCur++ ) ;

            //
            // Effectively reduce the graph tree
            //
            h_dawg_arr_node_it itNodeToRmCur = itNodeThisDepthToKeep + 1;
            for ( ; itNodeToRmCur != itNodeThisDepthSameHashEnd; itNodeToRmCur++ )
            {
                dawg_gnode_reduce_node(*itNodeToRmCur, *itNodeThisDepthSameHashEnd);
            }
        }
    }
  }
}


/**
  Determines whether the specified node has a child.
*/
dawg_bool_t dawg_gnode_has_child(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  return dawg_arr_node_size(pNode->h_dawg_arr_node_childs) > 0;
}


/**
  Get the character value of the specified node.
*/
unsigned char dawg_gnode_get_value(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  return pNode->cValue_;
}


/**
  Index difference between the specified node and its first child.
*/
int dawg_gnode_get_diff_index_with_fst_child(h_dawg_gnode hNode)
{
  dawg_gnode* pNode = (dawg_gnode*) hNode;
  assert(pNode);

  if (dawg_arr_node_size(pNode->h_dawg_arr_node_childs) > 0)
  {
    return ((dawg_gnode*) dawg_arr_node_begin(pNode->h_dawg_arr_node_childs))->nDawgIndex_ -
            pNode->nDawgIndex_;
  }

  return 0;
}


/**
  Recursively prints the nodes into the specified file stream.
*/
unsigned int dawg_print_nodes_recur
(
  h_dawg_gnode hNodeRoot, FILE* pOutFile,
  unsigned int nNodeNumber,
  unsigned int nFstChildNodeNumber
)
{
  dawg_gnode* pNodeRoot = (dawg_gnode*) hNodeRoot;
  assert(pNodeRoot);

  /* Print this node number */
  fprintf(pOutFile, "%u", nNodeNumber);

  /* Print this node infos */
  fprintf(pOutFile, " %c", pNodeRoot->cValue_);
  if (pNodeRoot->bEndOfWord_)
  {
    fprintf(pOutFile, " *");
  }
  fprintf(pOutFile, " %u %s %i [",
          pNodeRoot->nDepthGroup_,
          pNodeRoot->bEndOfDawgList_ ? "true" : "false",
          pNodeRoot->nDawgIndex_);

  /* Print the child numbers */
  h_dawg_arr_node_it itCurChild = dawg_arr_node_begin(pNodeRoot->h_dawg_arr_node_childs);
  h_dawg_arr_node_it itEndChild = dawg_arr_node_end(pNodeRoot->h_dawg_arr_node_childs);
  unsigned int nCurChildNodeNumber = nFstChildNodeNumber;
  for ( ; itCurChild != itEndChild; itCurChild++, nCurChildNodeNumber++)
  {
    fprintf(pOutFile, " %u", nCurChildNodeNumber);
  }
  fprintf(pOutFile, " ]\n");

  /* Recursively process the childs */
  itCurChild = dawg_arr_node_begin(pNodeRoot->h_dawg_arr_node_childs);
  itEndChild = dawg_arr_node_end(pNodeRoot->h_dawg_arr_node_childs);
  nCurChildNodeNumber = nFstChildNodeNumber;
  unsigned int nCurChildChildNodeNumber = nFstChildNodeNumber + dawg_arr_node_size(pNodeRoot->h_dawg_arr_node_childs);
  for ( ; itCurChild != itEndChild; itCurChild++, nCurChildNodeNumber++)
  {
    nCurChildChildNodeNumber = dawg_print_nodes_recur(*itCurChild, pOutFile,
                                                      nCurChildNodeNumber,
                                                      nCurChildChildNodeNumber);
  }
  return nCurChildChildNodeNumber;
}


/**
  Prints the tree the root of which is specified and into the specified out stream.
*/
void dawg_gnode_print(h_dawg_gnode hNodeRoot, FILE* pOutFile)
{
  dawg_print_nodes_recur(hNodeRoot, pOutFile, 0, 1);
}

